package Acwing.搜索与图论;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @Title: dijkstraFindMinValue2
 * @Author 贾金博
 * @Package Acwing.搜索与图论
 * @Date 2025/4/11 下午10:21
 * @description: Dijkstra求最短路II
 */
public class dijkstraFindMinValue2 {

    // 堆优化后的 Dijkstra算法
    private static int n;
    private static int m;
    private static int[] dis;
    private static int[] h;
    public static int[] w;
    public static int[] e;
    public static int[] ne;
    private static boolean[] st;
    public static int idx; // 表示节点的下标

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        init();

        while(m -- > 0 ) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            add(x, y, z);
        }

        dijkstra();

        if(dis[n] == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(dis[n]);
        }
    }

    private static void dijkstra() {
        dis[1] = 0;
        PriorityQueue<myNode> q = new PriorityQueue<>();
        q.add(new myNode(1, 0));
        while(!q.isEmpty()) {
            myNode t = q.poll();

            if(st[t.node]) {
                continue;
            }
            st[t.node] = true;

            for(int i = h[t.node]; i != -1; i = ne[i]) {
                int node = e[i];
                int val = w[i];

                if(dis[node] > dis[t.node] + w[i]) {
                    dis[node] = dis[t.node] + w[i]; // 加的是 对应的边的值
                    q.add(new myNode(node, dis[node]));
                }
            }
        }
    }


    public static void init() {
        dis = new int[n + 10];
        h = new int[n + 10];
        w = new int[m * 2 + 10];
        e = new int[m * 2 + 10];
        ne = new int[m * 2 + 10];
        st = new boolean[n + 10];

        Arrays.fill(dis, Integer.MAX_VALUE);
        Arrays.fill(h, -1);
        Arrays.fill(st, false);

    }

    public static void add(int x, int y, int z) {
        // 在x y 之间插入的边长为 z 的
        e[idx] = y;
        w[idx] = z;
        ne[idx] = h[x];
        h[x] = idx ++ ;
    }



}

class myNode implements Comparable<myNode> {
    int node;
    int val;

    public myNode(int node, int val) {
        this.node = node;
        this.val = val;
    }

    // 自定义排序规则
    @Override
    public int compareTo(myNode myNode) {
        return this.val - myNode.val; // 这样就是按照从小到大的排序 小根堆
    }

}
